package leetcode.top100;

/**
 * 【剑指offer51】
 * 在一个长度为n的数组里的所有数字都在0到n-1的范围内。
 * 数组中某些数字是重复的，但不知道有几个数字是重复的。
 * 也不知道每个数字重复几次。请找出数组中任意一个重复的数字。
 * 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
 * <p>
 * 其他相关问题见{@link leetcode.a_总结分布.Code02_数组中缺失或重复数字}
 *
 * @date 2020/4/15 13:18
 */
public class Code287_FindRepeatNum1 {
//    方式1：两次循环，时间O(n²),空间O(1)
//    方式2：排序，时间O(nlogN),空间O(1)
//    方式3：借助桶或hashSet，时空都是O(n)
    public static int bucketProcess(int []nums){
        //len = n
        int len = nums.length;
        int[]bucket = new int[len];
        //数字在0-n-1之间。准备n个桶,0,1,...,n-1号。
        for(int i=0 ; i < len; i++){
            if(bucket[nums[i]] >= 1) return nums[i];
            bucket[nums[i]]++;
        }

        return -1;
    }
    //方式4：归位思想
    public int duplicate(int[] numbers) {
        int length = numbers.length;
        for (int i = 0; i < length; i++) {
            //当前位置arr[i]!=i,则一直交换，把arr[i]=index与arr[index]交换，
            //直到arr[i]==i,如果index == arr[index],则说明重复
            while (numbers[i] != i) {
                int index = numbers[i];
                if (index == numbers[index]) {
                    return index;
                }
                //否则交换
                swap(numbers, index, i);
            }
        }
        return -1;
    }

    /**
     * 方式5：标记思想
     * 注意要特殊去处理nums[i] = 0情况，如｛1，0，1｝，此时重复的是1，但是nums[1]不满足<0
     */
    public static int duplicate5(int[] nums) {
        if(nums == null || nums.length <=1){
            return -1;
        }
        boolean repeat = false;
        for(int i=0 ; i< nums.length;i++){
            int index = Math.abs(nums[i]);
            if(nums[index] < 0) {
                return index;
            }
            nums[index] = -nums[index];
        }
        return -1;
    }


    private void swap(int[] nums, int i, int j) {
        if (i != j) {
            nums[i] = nums[i] ^ nums[j];
            nums[j] = nums[i] ^ nums[j];
            nums[i] = nums[i] ^ nums[j];
        }
    }




}
